package org.lql.algo.codecrush.hot100.skill;

/**
 * @author: liangqinglong
 * @date: 2025-10-13 20:53
 * @description: 287. 寻找重复数 <a href="https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class FindDuplicate {

	public int findDuplicate(int[] nums) {
		int left = 1;
		int right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			int count = 0;
			for (int num : nums) {
				if (num <= mid) {
					count++;
				}
			}
			if (count > mid) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return left;
	}

	public static void main(String[] args) {
		FindDuplicate findDuplicate = new FindDuplicate();
		int[] nums = {1, 3, 4, 2, 2};
		System.out.println(findDuplicate.findDuplicate(nums));
	}
}
